package com.future;

import com.future.util.TreeNode;

/**
 * 给定一个二叉树，判断它是否是高度平衡的二叉树。
 */
public class Solution_isBalanced_110 {

    public static void main(String[] args) {
        TreeNode head = new TreeNode(1,
                new TreeNode(2, new TreeNode(4, new TreeNode(5), null), null), new TreeNode(3));
        System.out.println(isBalanced(head));
    }

    public static boolean isBalanced(TreeNode root) {
        return process(root).isBalanced;
    }

    private static Info process(TreeNode root) {
        if (root == null) {
            return new Info(true, 0);
        }
        // 拿到左树的信息
        Info leftInfo = process(root.left);
        // 拿到右树的信息
        Info rightInfo = process(root.right);
        // 当前高度是左子树|右子树的最大加+1
        int height = Math.max(leftInfo.height, rightInfo.height) + 1;
        boolean isBanced = leftInfo.isBalanced && rightInfo.isBalanced
                && Math.abs(leftInfo.height - rightInfo.height) < 2;
        return new Info(isBanced, height);
    }

    /**
     * 记录当前树的是否平衡和高度
     */
    private static class Info {
        public boolean isBalanced;
        public int height;

        public Info(boolean isBalanced, int height) {
            this.isBalanced = isBalanced;
            this.height = height;
        }
    }
}
